package com.example.link;

// 链表反转 - 递归方式
public class recursion {

    private static class LinkNode {

        int val;
        LinkNode next;

        public LinkNode(int val, LinkNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 递归
    private static LinkNode recursion(LinkNode head) {
        // head等于null表示传入链表本身为null，如果head.next等于null代表到达最后一个元素
        if (head == null || head.next == null) {
            return head;// 直接返回这个head结点
        }
        LinkNode newHead = recursion(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }


    public static void main(String[] args) {

        LinkNode node5 = new LinkNode(5, null);
        LinkNode node4 = new LinkNode(4, node5);
        LinkNode node3 = new LinkNode(3, node4);
        LinkNode node2 = new LinkNode(2, node3);
        LinkNode node1 = new LinkNode(1, node2);

        LinkNode prev = recursion(node1);
        System.out.println(prev);



    }

}
